package org.sselab.leetcode;

import java.util.Arrays;
import java.util.List;
import java.util.Optional;

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}

class Solution1 {
  public TreeNode sortedListToBST(ListNode head) {
    if (head == null) {
      return null;
    }
    if (head.next == null) {
      return new TreeNode(head.val);
    }
    return buildTree(head, null);
  }

  private TreeNode buildTree(ListNode begin, ListNode end) {
    if (begin == null) {
      return null;
    }
    if (begin == end) {
      return new TreeNode(begin.val);
    }
    List<ListNode> list = getMidListNode(begin, end);
    TreeNode root = new TreeNode(list.get(0).val);
    if (list.get(1) != null) {
      root.left = buildTree(begin, list.get(1));
    }
    root.right = buildTree(list.get(0).next, end);
    return root;
  }

  private void scanListNode(ListNode begin, ListNode end) {
    while (begin != end) {
      begin = begin.next;
    }
    Optional.ofNullable(begin).ifPresent(node -> System.out.print(node.val));
  }

  /**
   * 根据end是否为空分别应对两种不同的传参情况!
   *
   * @param head 头节点
   * @param end  尾结点,可能直接传入空
   * @return
   */
  public List<ListNode> getMidListNode(ListNode head, ListNode end) {
    ListNode oneStep, twoStep, pre = null;
    oneStep = twoStep = head;
    scanListNode(head, end);
    if (end == null) {
      while (twoStep.next != null && twoStep.next.next != null) {
        pre = oneStep;
        oneStep = oneStep.next;
        twoStep = twoStep.next.next;
      }
    } else {
      while (twoStep != end && twoStep.next != end) {
        pre = oneStep;
        oneStep = oneStep.next;
        twoStep = twoStep.next.next;
      }
    }
    return Arrays.asList(oneStep, pre);
  }
}
